Криптосистема Блюма — Гольдвассер

Криптосистема Блюма — Гольдвассер — одна из схем шифрования с открытым ключом, основанная на сложности факторизации больших целых чисел. Этот алгоритм шифрования был предложен Мануэлем Блюмом и Шафи Гольдвассер в 1984 году.

Пусть m₁, m₂, … , m_m — последовательность бит открытого текста. В качестве параметров криптосистемы выбираем n=pq — число Блюма, x₀ — случайное число из Z_n, взаимно простое с N.

В качестве открытого ключа для шифрования выступает n, в качестве секретного ключа для расшифрования — пара (p, q).

Для того, чтобы зашифровать открытый текст, обладатель открытого ключа выбирает x₀. На основе BBS-генератора по вектору инициализации x₀ получают последовательность квадратов x₁, x₂, … , x_m, по которой получают последовательность младших бит b₁, b₂, …, b_m. Путём гаммирования с этой последовательностью битов открытого текста и получают шифрованный текст c_i=m_i⊕b_i, i=1,2,…,m.

Шифрограмма, которая пересылается обладателю секретного ключа, есть (c₁,c₂,…,c_m, x_m+1). После формирования шифрограммы последовательность x_i, i=0,1,…,m уничтожается, и при следующем сеансе связи отправитель выбирает новое x₀.

Получатель шифрограммы восстанавливает по x_m+1 последовательность главных корней x_m, … , x₁ и последовательность их младших бит b₁, b₂, …, b_m, а затем расшифровывает шифрограмму: m_i=c_i⊕b_i , i=1,2,…,m.

Как происходит шифрование сообщений

Предположим, что Боб хочет послать сообщение «m» Алисе:

1. Боб сначала кодирует [math]\displaystyle{ m }[/math] в виде строки из [math]\displaystyle{ L }[/math] бит[math]\displaystyle{ (m_0, \dots, m_{L-1}) }[/math]
2. Боб выбирает случайный элемент [math]\displaystyle{ r }[/math], где [math]\displaystyle{ 1 \lt r \lt N }[/math], и вычисляет [math]\displaystyle{ x_0 = r^2~mod~N }[/math]
3. Боб использует псевдослучайные числа для генерации случайных чисел [math]\displaystyle{ L }[/math], следующим образом:
   1. Для [math]\displaystyle{ i=0 }[/math] до [math]\displaystyle{ L-1 }[/math]:
   2. Ряд [math]\displaystyle{ b_i }[/math] равен наименьшему значению бита [math]\displaystyle{ x_i }[/math];
   3. Увеличиваем [math]\displaystyle{ i }[/math] ;
   4. Вычисляем [math]\displaystyle{ x_i = (x_{i-1})^2~mod~N }[/math]
4. Вычисляем зашифрованный текст с помощью гамирования ключевого потока [math]\displaystyle{ {\vec c} = {\vec m} \oplus {\vec b}, y=x_{L}=x_{L-1}^{2}~mod~N }[/math]
5. Боб отправляет зашифрованный текст[math]\displaystyle{ (c_0, \dots, c_{L-1}), y }[/math]

Как происходит расшифрование сообщений

Алиса получает [math]\displaystyle{ (c_0, \dots, c_{L-1}), y }[/math]. Она может восстановить «m», используя следующую процедуру:

1. Используя разложение на множители [math]\displaystyle{ (p, q) }[/math] Алиса получает [math]\displaystyle{ r_p = y^{((p+1)/4)^{L}}~mod~p }[/math] и [math]\displaystyle{ r_q = y^{((q+1)/4)^{L}}~mod~q }[/math].
2. Вычисление начального источника [math]\displaystyle{ x_0=q(q^{-1}~{mod}~p)r_p + p(p^{-1}~{mod}~q)r_q~{mod}~N }[/math]
3. Начиная с [math]\displaystyle{ x_0 }[/math] повторно вычисляем битовый вектор [math]\displaystyle{ {\vec b} }[/math] используя генератор BBS, как в алгоритм шифрования.
4. Вычисляем текст с помощью гаммирование ключивым потоком с зашифрованным текстом [math]\displaystyle{ {\vec m} = {\vec c} \oplus {\vec b} }[/math].

Алиса восстановила исходный текст [math]\displaystyle{ m=(m_0, \dots, m_{L-1}) }[/math]

Эффективность

В зависимости от размера обычного текста BG может задействовать больше или меньше вычислительных ресурсов чем RSA. RSA использует оптимизированный способ шифрования, чтобы минимизировать время шифрования, шифрование RSA будет как правило выигрывать у BG во всём, кроме самых коротких сообщений. Поскольку время расшифрования RSA нестабильно, то возведение в степень по модулю может потребовать столько же ресурсов как для расшифровки BG зашифрованного текста той же самой длины. BG более эффективно к более длинным зашифрованным текстам, в которых RSA требует многократного отдельного шифрования. В этих случаях BG более эффективно.

Ссылки

• M. Blum, S. Goldwasser, «An Efficient Probabilistic Public Key Encryption Scheme which Hides All Partial Information», Proceedings of Advances in Cryptology — CRYPTO '84, pp. 289—299, Springer Verlag, 1985.
• Menezes, Alfred; van Oorschot, Paul C.; and Vanstone, Scott A. Handbook of Applied Cryptography. CRC Press, October 1996. ISBN 0-8493-8523-7